package 代码记录.Bit48天集训;

import java.util.Scanner;

/**1.发邮件
 * 2.最长上升子序列
 * @author zx
 * @create 2022-06-29 19:40
 */
public class day_40 {
    /**
     经典错排问题

     假设：dp[i]表示i封信总共装错的总数
     如果A装入到b的信封中：
     将B信装入到A的信封中：A ->b  B -> a  出错的总数：取决于剩余的n-2封信：dp[i - 2]
     将B信装入到除A以外的其它信封：剩余n - 1封信放错的可能性dp[i - 1]
     综上得到
     dp[i] = (i-1) * (dp(i-2) + dp(i-1))
     特殊地,dp[1] = 0, dp[2] = 1.
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            System.out.println(helper(n));
        }
    }
    private static long helper(int n){
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        for(int i = 3;i <= n;i++){
            dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
        }
        return dp[n];
    }

    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] arr = new int[n];
            for(int i = 0;i < n;i++){
                arr[i] = sc.nextInt();
            }
            System.out.println(dfs(arr));
        }
    }
    private static int dfs(int[] arr){
        //dp[i]:[0,i]的最长递增子序列的长度为dp[i]
        int[] dp = new int[arr.length];
        for(int i = 0;i < arr.length;i++){
            dp[i] = 1;
        }
        int res = 0;
        for(int i = 0;i < arr.length;i++){
            for(int j = 0;j < i;j++){
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}
